Обсуждение:Полнота по Тьюрингу
Нужны ссылки на источники, больше истории. Почему полнота "по Тьюрингу", а не "по Посту" (см. машина Поста)? У каких российских учёных есть аналоги (пусть и позже иностранных, но оригинальные исследования, а не работа переводчиков)? 77.37.160.152 03:39, 17 октября 2023 (UTC)
ANSI C не полон по Тьюрингу, потому что не может адресовать бесконечное количество памяти. Это хороший пример различия теории и практики :) --- Lispnik
[ненормативная лексика] Где сказано что не может? 212.19.157.154
- Урезал ваш комментарий, и просьба подписываться (--~~~~). --Yurik 19:08, 22 Апр 2005 (UTC)
- Первое, согласно стандарту, char должен иметь конечный размер. Второе, все типы должны иметь конечный размер в char (sizeof). Т.о. указатели могут адресовать не более чем (MAX_CHAR_VALUE-MIN_CHAR_VALUE)^(sizeof(void*)) элементов, где ^ означает возведение в степень. --- Lispnik
- Из того, что указатели не могут что-то там адресовать, ничего не следует. Можно использовать относительные указатели (продолжение по смещению +N символов), и их можно использовать любое количество (см. "связный список"). 77.37.160.152 03:39, 17 октября 2023 (UTC)
Неверное определение. Неверно говорить, что полные по Тьюрингу исполнители -- это те, которых можно сэмулировать на Универсальной Машине Тьюринга. Универсальная Машина Тьюринга может эмулировать только машины Тьюринга, в том числе саму себя. На вход она может получать только описание машины тьюринга и входа для этой машины. Машину Поста, например, она не может эмулировать в принципе. ПРЕДЛОЖЕНИЯ:
- Полноту по Тьюрингу включить в статью про Машину Тьюринга (что я уже сделал). А Здесь сделать редирект.
- Можно сделать также статью Языки программирования полные по Тьюрингу, либо сделать эту тему разделом статьи Машина Тьюринга.
- Использовать слово "имитация", а не "эмуляция". -- greck 08:06, 18 апреля 2006 (UTC)
- Полнота по Тьюрингу — это важное понятие, достойное отдельной статьи. Она не сводится только к машине Тьюринга и даже важнее её, поэтому я против включения. Скорее статью о машине Тьюринга можно сделать частью статьи о полноте по Тьюрингу, как пример вычислителя, полного по Тьюрингу. С остальной критикой я согласен. Надо подумать, проконсультироваться с литературой типа книг Маркова или Роджерса и переписать статью. Lispnik 08:16, 20 апреля 2006 (UTC)
Я вот почитал определения и так никуя и не понял - пишите понятно (Дмитрий)
- поддерживаю. нихуя не понятно и из примеров. 77.176.20.19 19:40, 7 июля 2008 (UTC)
Взаимоисключающие параграфы: полнота характеризует исполнитель, и некоторые формальные грамматики не являются полными. Грамматика - не исполнитель.
Тьюринг полнота времени компиляции в Haskell "появляется", только если использовать расширения к стандарту языка, доступные в одном из компиляторов. Хотя нужно признать, что этот компилятор и эти его расширения очень популярны. Подробности, например, здесь: http://www.haskell.org/pipermail/haskell/2006-August/018355.html Ierton 19:40, 10 апреля 2011 (UTC)